Binary trees

Introducción

Un Árbol Binario es un tipo de estructura de datos donde cada nodo tiene por lo menos dos hijos (hijo izquierdo e hijo derecho). Los Árboles Binarios son usados para implementar árboles de busqueda binaria, y son usados para buscar y ordenar eficientemente. Un árbol binario es un caso especial de un árbol K-ario, donde K es 2. Algunas operaciones para los árboles binarios incluyen inserción, supresión, y poder recorrerlos. La dificultad de realizar estas operaciones va a depender de si el árbol está balanceado y si los nodos son nodos hijos o nodos padres. Para un árbol balanceado el profundo de los nodos de los subárboles izquierdos y derechos difieren por 1 o menos. Esto permite una profundidad predecible también conocida como altura. Esta es la medida de raíz a hoja (padre e hijo), donde la raíz es 0 y los nodos siguientes son (1,2..n). Esto puede ser expresado como la parte entera de log₂(n) donde n es el número de nodos en el árbol.

        g                  s                  9
       / \                / \                / \
      b   m              f   u              5   13
     / \                    / \                /  \
    c   d                  t   y              11  15

Las operaciones realizadas requieren buscar en una de dos maneras principales: Búsqueda de "Profundidad Primero" y Búsqueda de "Amplitud Primero". Depth-first search (DFS, Profunidad Primero) es un algoritmo para recorrer o buscar en estructuras de árboles o gráficos de datos. Uno empieza en la raíz y explora tan lejos como puede entre cada rama antes de volver atrás. Hay tres tipos de recorrido en este tipo de búsqueda: pre orden visita, izquierda, derecha, en orden izquierda, visita, derecha, post orden izquierda, derecha, visita. Breadth-first search (BFS, Amplitud Primero) es un algoritmo para recorrer y buscar estructuras de árboles o gráficos. En orden de nivel, donde visitamos cada nodo en un nivel antes de ir a un nivel más bajo.

Ejercicio

Debajo hay una implementación de un árbol binario que tiene capacidades de imprimirse e insertar elementos en él. Este árbol está ordenado pero no balanceado. Este ejemplo mantiene su orden a la hora de insertar.

Cambia la rutina de impresión a búsqueda de profundidad primero con pre orden.